//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 
//
// 有效字符串需满足： 
//
// 
// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "()[]{}"
//输出：true
// 
//
// 示例 3： 
//
// 
//输入：s = "(]"
//输出：false
// 
//
// 示例 4： 
//
// 
//输入：s = "([)]"
//输出：false
// 
//
// 示例 5： 
//
// 
//输入：s = "{[]}"
//输出：true 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 仅由括号 '()[]{}' 组成 
// 
// Related Topics 栈 字符串 
// 👍 3116 👎 0


import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)

class Solution {
    private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
        put('{','}'); put('[',']'); put('(',')'); put('?','?');
    }};
    public boolean isValid(String s) {
        if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        LinkedList<Character> stack = new LinkedList<Character>() {{ add('?'); }};
        for(Character c : s.toCharArray()){
            if(map.containsKey(c)) stack.addLast(c);
            else if(map.get(stack.removeLast()) != c) return false;
        }
        return stack.size() == 1;
    }
}

//leetcode submit region end(Prohibit modification and deletion)
class Solution {
    public boolean isValid(String s) {
        Stack<Character> characterStack = new Stack<>();
//        '('，')'，'{'，'}'，'['，']'
        Character topC;
        for (Character c : s.toCharArray()) {
            if ("({[".indexOf(c) >= 0)  {
                characterStack.push(c);
            }else if (")]}".indexOf(c) >= 0){

                if (characterStack.isEmpty()){
                    return false;
                }
                topC = characterStack.pop();
                if ('(' == topC && ')' == c){
                    continue;
                }
                if ('{' == topC && '}' == c){
                    continue;
                }
                if ('[' == topC && ']' == c){
                    continue;
                }
                return false;
            }
        }

        return characterStack.isEmpty();

    }
}